package _07_串;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class _3_无重复字符的最长子串 {

    public static void main(String[] args) {
        _3_无重复字符的最长子串 v = new _3_无重复字符的最长子串();
        String str = "abcabcbb";
        System.out.println(v.lengthOfLongestSubstring1(str));
    }


    // 滑动窗口
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        if (chars.length == 0) return 0;
        HashSet<Character> set = new HashSet<>();
        int right = -1;
        int max = 1;
        for (int i = 0; i < chars.length; i++) {
            // 滑动窗口左指针移动
            if (i != 0) {
                set.remove(chars[i - 1]);
            }
            // 滑动窗口右指针移动
            while (right + 1 < chars.length && !set.contains(chars[right + 1])) {
                set.add(chars[++right]);
            }
            max = Math.max(max, right - i + 1);
        }
        return max;
    }

    // 优化为单字节
    public int lengthOfLongestSubstring3(String s) {
        if (s.length() == 0) return 0;
        char[] chars = s.toCharArray();
        int[] ints = new int[128];
        Arrays.fill(ints, -1);
        ints[chars[0]] = 0;
        // 由于只用到了前面一个数据，所以可以优化为变量
        int prev = 0;
        int max = 1;
        for (int i = 1; i < chars.length; i++) {
            // 查看当前字符串出现的索引位置
            int index = ints[chars[i]];
            if (index >= prev) {
                prev = index + 1;
            }
            ints[chars[i]]  = i;
            max = Math.max(max, i - prev + 1);
        }
        return max;
    }

    public int lengthOfLongestSubstring2(String s) {
        if (s.length() == 0) return 0;
        char[] chars = s.toCharArray();
        // 由于只用到了前面一个数据，所以可以优化为变量
        int dp = 0;
        HashMap<Character, Integer> indexs = new HashMap<>();
        indexs.put(chars[0], 0);
        int max = 1;
        for (int i = 1; i < chars.length; i++) {
            // 查看当前字符串出现的索引位置
            Integer index = indexs.getOrDefault(chars[i], -1);
            if (index >= dp) {
                dp = index + 1;
            }
            indexs.put(chars[i], i);
            max = Math.max(max, i - dp + 1);
        }
        return max;
    }

    // 假设i是以某个字符结尾的最长无重复子串
    // j = i - 1; li是以j结尾的最长无重复子串的开始索引
    // pi 保存的是上一次出现此字符的索引位置
    public int lengthOfLongestSubstring1(String s) {
        char[] chars = s.toCharArray();
        // 初始值
        // 存放以i结尾的最长无重复子串
        int[] nums = new int[chars.length];
        nums[0] = 0;
        // 存放当前字符上一次出现的索引位置
        HashMap<Character, Integer> indexs = new HashMap<>();
        indexs.put(chars[0], 0);
        int max = 1;
        for (int i = 1; i < chars.length; i++) {
            int j = i - 1;
            // 查看当前字符串出现的索引位置
            Integer index = indexs.getOrDefault(chars[i], -1);
            if (index < nums[j]) {
                nums[i] = nums[j];
            } else {
                nums[i] = index + 1;
            }
            indexs.put(chars[i], i);
            max = Math.max(max, i - nums[i] + 1);
        }
        return max;
    }

}
